package org.example;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// 多叉树的递归/层序遍历
// https://labuladong.online/algo/data-structure-basic/n-ary-tree-traverse-basic/
public class MultiTree {
    // 二叉树
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }

    class Node {
        int val;
        List<Node> children;
    }

    // 递归遍历（DFS）
    // 二叉树的遍历框架
    void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        // 前序遍历
        traverse(root.left);
        // 中序遍历
        traverse(root.right);
        // 后序遍历
    }

    // N叉树的遍历框架
    void traverse(Node root) {
        if (root == null) {
            return;
        }
        // 前序遍历
        for (Node child : root.children) {
            traverse(child);
        }
        // 后序遍历
    }

    // 层序遍历（BFS）
    // 写法一：第一种层序遍历写法，无法记录节点深度
    static class Func1 {
        void levelOrderTraverse(Node root) {
            if (root == null) {
                return;
            }
            Queue<Node> q = new LinkedList<>();
            q.offer(root);
            while (!q.isEmpty()) {
                Node cur = q.poll();
                // 访问cur节点
                System.out.println(cur.val);

                // 把cur的所有子节点加入队列
                for (Node child : cur.children) {
                    q.offer(child);
                }
            }
        }
    }

    // 层序遍历（BFS）
    // 写法二：第二种层序遍历写法，能够记录节点深度
    static class Func2 {
        void levelOrderTraverse(Node root) {
            if (root == null) {
                return;
            }
            Queue<Node> q = new LinkedList<>();
            q.offer(root);
            // 记录当前遍历到的层数（根节点视为第一层）
            int depth = 1;
            while (!q.isEmpty()) {
                int sz = q.size();
                // 遍历当前层的所有节点：通过for循环处理sz次，每次从队列中取出一个节点（当前层的节点）。
                for (int i = 0; i < sz; i++) {
                    Node cur = q.poll();
                    // 访问cur节点，同时知道它所在的层数
                    System.out.println("depth = " + depth + ", val = " + cur.val);

                    for (Node child : cur.children) {
                        q.offer(child);
                    }
                }
                depth++;
            }
        }
    }

    // 层序遍历（BFS）
    // 写法三：第三种能够适配不同权重边的写法
    static class Func3 {
        class State {
            Node node;
            int depth;

            public State(Node node, int depth) {
                this.node = node;
                this.depth = depth;
            }
        }

        void levelOrderTraverse(Node root) {
            if (root == null) {
                return;
            }
            Queue<State> q = new LinkedList<>();
            // 记录当前遍历到的层数（根节点视为第1层）
            q.offer(new State(root, 1));
            while (!q.isEmpty()) {
                State state = q.poll();
                Node cur = state.node;
                int depth = state.depth;
                // 访问cur节点，同时知道它所在的层数
                System.out.println("depth = " + depth + ", val = " + cur.val);
                for (Node child : cur.children) {
                    q.offer(new State(child, depth + 1));
                }
            }
        }
    }

    // 589. N 叉树的前序遍历
    // 给定一个 n 叉树的根节点  root ，返回 其节点值的 前序遍历 。
    // n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
    // 输入：root = [1,null,3,2,4,null,5,6]
    // 输出：[1,3,5,6,2,4]

    // 输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
    // 输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]
    static class Preorder{
        List<Integer> res = new ArrayList<>();
        public List<Integer> preorder(Node root) {
            traverse(root);
            return res;
        }

        void traverse(Node root){
            if (root == null){
                return;
            }
            res.add(root.val);
            for(Node ch : root.children){
                traverse(ch);
            }
        }
    }

    // 590. N 叉树的后序遍历
    // 给定一个 n 叉树的根节点 root ，返回 其节点值的 后序遍历 。
    // n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
    // 输入：root = [1,null,3,2,4,null,5,6]
    // 输出：[5,6,3,2,4,1]
    // 输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
    // 输出：[2,6,14,11,7,3,12,8,4,13,9,10,5,1]
    static class Postorder{
        List<Integer> res = new ArrayList<>();
        public List<Integer> postorder(Node root) {
            traverse(root);
            return res;
        }

        void traverse(Node root){
            if (root == null){
                return;
            }
            for(Node ch : root.children){
                traverse(ch);
            }
            res.add(root.val);
        }
    }

}
